package com.github.algorithm.sort;


/**
 * 内排序
 * 交换排序, 包含冒泡排序和快速排序
 * 插入排序, 包含直接插入排序和希尔排序
 * 选择排序, 包含直接选择排序和堆排序
 * 归并排序
 *
 * @author Stephen
 * @date 2020/6/7 11:09
 */
public class InternalSort {

    /**
     * 冒泡排序
     * 从小到大排序
     * 时间复杂度O(n^2)
     *
     * @param array 要排序的数组
     */
    public static void bubbleSort(int[] array) {

        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                }
            }
        }
    }

    /**
     * 快速排序
     * 从小到大排序
     *
     * @param array 要排序的数组
     * @param left  左边元素
     * @param right 右边元素
     */
    public static void quickSort(int[] array, int left, int right) {
        if (left >= right) return;
        int pivot = getPivot(left, right); //select the pivot of the array
        swap(array, pivot, right); //set the pivot to the right of the array
        pivot = partition(array, left, right); //set the pivot to the correct position
        quickSort(array, left, pivot - 1); //sort the left partition array
        quickSort(array, pivot + 1, right); //sort the right partition array
    }

    /**
     * get the pivot of an array which always prefers the middle position
     *
     * @return pivot of an array
     */
    public static int getPivot(int left, int right) {
        return (left + right) / 2;
    }


    /**
     * 获取数组的索引位置
     *
     * @param array 要排序的数组
     * @param left  左边位置
     * @param right 右边位置
     * @return 索引位置
     */
    public static int partition(int[] array, int left, int right) {
        int l = left;
        int r = right;
        int temp = array[l]; //set the left to temp
        while (l != r) {
            while (array[l] <= temp && r > l) {
                l++;
                if (l < r) {
                    array[r] = array[l];
                    r--;
                }
            }
            while (array[r] >= temp && r > l) {
                r--;
            }
            if (l < r) {
                array[l] = array[r];
                l++;
            }
        }
        array[l] = temp; //set the temp to left
        return l;
    }

    //插入排序
    public static void insertSort(int[] array) {
        int i, j, temp;
        //外层循环从1开始
        for (i = 1; i < array.length; i++) {
            temp = array[i];
            j = i - 1;
            //内层循环从i-1开始
            while (j >= 0 && temp < array[j]) {
                array[j + 1] = array[j];
                j = j - 1;
            }
            //此时j+1就是记录i的正确位置
            array[j + 1] = temp;
        }
    }

    public static void shellSort(int[] array) {
        int i, delta;
        for (delta = array.length / 2; delta > 0; delta /= 2) {
            for (i = 0; i < delta; i++) {
                modInsertSort(null, array.length - i, delta);
            }
        }
    }

    public static void modInsertSort(int[] array, int len, int delta) {
        int i, j;
        for (i = delta; i < len; i += len)
            for (j = i; j >= delta; j -= delta)
                if (array[j] < array[j - delta])
                    swap(array, j, j - delta);
                else break;
    }

    //选择排序
    public static void selectSort(int[] array) {
        int i, j, smallest;
        for (i = 0; i < array.length - 1; i++) {
            smallest = i;
            for (j = i + 1; j < array.length; j++)
                if (array[j] < array[smallest])
                    smallest = j;
            swap(array, i, smallest);
        }
    }

    //heap sort
    public static void heapSort(int[] array) {
        int len = array.length;
        buildMaxHeap(array, len);
        for (int i = len - 1; i > 0; i--) {
            swap(array, 0, i);
            len--;
            heapify(array, 0, len);
        }
    }

    public static void buildMaxHeap(int[] array, int len) {
        for (int i = len / 2; i >= 0; i--)
            heapify(array, i, len);
    }

    public static void heapify(int[] array, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
        if (left < len && array[left] > array[largest]) {
            largest = left;
        }
        if (right < len && array[right] > array[largest]) {
            largest = right;
        }
        if (largest != i) {
            swap(array, i, largest);
            heapify(array, largest, len);
        }
    }


    //merge sort

    public static void mergeSort(int[] array) {
        int left = 0;
        int right = array.length - 1;
        int[] temp = new int[right - left + 1];
        mergeSort(array, temp, left, right);
    }

    public static void mergeSort(int[] array, int[] temp, int left, int right) {
        int middle;
        if (left < right) {
            middle = (left + right) / 2;
            mergeSort(array, temp, left, middle);
            mergeSort(array, temp, middle + 1, right);
            merge(array, temp, left, right, middle);
        }
    }

    public static void merge(int[] array, int[] temp, int left, int right, int middle) {
        int i, j, leftIndex, rightIndex;
        for (j = left; j <= right; j++)
            temp[j] = array[j];

        leftIndex = left;
        rightIndex = middle + 1;
        i = left;
        while (leftIndex <= middle && rightIndex <= right)
            if (temp[leftIndex] <= temp[rightIndex])
                array[i++] = temp[leftIndex++];
            else array[i++] = temp[rightIndex++];

        while (leftIndex <= middle)
            array[i++] = temp[leftIndex++];
        while (rightIndex <= right)
            array[i++] = temp[rightIndex++];
    }

    //mod merge sort

    public static void modMergeSort(int[] array, int[] temp, int left, int right) {
        int middle;
        if (right - left + 1 > 28) {
            middle = (left + right) / 2;
            modMergeSort(array, temp, left, middle);
            modMergeSort(array, temp, middle + 1, right);
            modMerge(array, temp, left, right, middle);
        }
        //user insertSort
        else {


        }
    }

    public static void modMerge(int[] array, int[] temp, int left, int right, int middle) {
        int i, j, k, leftIndex, rightIndex;
        //copy left sub array
        for (i = left; i <= middle; i++)
            temp[i] = array[i];
        //copy right sub array in inverse order
        for (j = 1; j <= right - middle; j++)
            temp[right - j + 1] = array[j + middle];
        //merge the smaller element into the array
        for (leftIndex = left, rightIndex = right, k = left; k <= right; k++)
            if (temp[leftIndex] <= temp[rightIndex])
                array[k] = temp[leftIndex++];
            else array[k] = temp[rightIndex--];
    }

    /**
     * swap the position of i and j
     *
     * @param array the array to be sorted
     */
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
